Clover icon

compiler

  1. Project Clover database Mon Jan 2 2023 15:09:37 MST
  2. Package com.google.javascript.jscomp

File DataFlowAnalysis.java

 

Coverage histogram

../../../../img/srcFileCovDistChart9.png
54% of files have more coverage

Code metrics

52
141
32
5
579
306
62
0.44
4.41
6.4
1.94

Classes

Class Line # Actions
DataFlowAnalysis 85 81 35 4
0.96969797%
DataFlowAnalysis.FlowState 331 12 7 4
0.789473778.9%
DataFlowAnalysis.MaxIterationsExceededException 382 1 1 0
1.0100%
DataFlowAnalysis.BranchedForwardDataFlowAnalysis 389 33 12 4
0.9215686392.2%
DataFlowAnalysis.BranchedFlowState 485 14 7 11
0.4761904847.6%
 

Contributing tests

This file is covered by 7434 tests. .

Source view

1    /*
2    * Copyright 2008 The Closure Compiler Authors.
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License");
5    * you may not use this file except in compliance with the License.
6    * You may obtain a copy of the License at
7    *
8    * http://www.apache.org/licenses/LICENSE-2.0
9    *
10    * Unless required by applicable law or agreed to in writing, software
11    * distributed under the License is distributed on an "AS IS" BASIS,
12    * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13    * See the License for the specific language governing permissions and
14    * limitations under the License.
15    */
16   
17    package com.google.javascript.jscomp;
18   
19    import com.google.common.base.Objects;
20    import com.google.common.base.Preconditions;
21    import com.google.common.collect.Lists;
22    import com.google.common.collect.Sets;
23    import com.google.javascript.jscomp.ControlFlowGraph.Branch;
24    import com.google.javascript.jscomp.NodeTraversal.AbstractPostOrderCallback;
25    import com.google.javascript.jscomp.Scope.Var;
26    import com.google.javascript.jscomp.graph.Annotation;
27    import com.google.javascript.jscomp.graph.DiGraph.DiGraphNode;
28    import com.google.javascript.jscomp.graph.LatticeElement;
29    import com.google.javascript.rhino.Node;
30   
31    import java.util.ArrayList;
32    import java.util.Comparator;
33    import java.util.Iterator;
34    import java.util.List;
35    import java.util.Set;
36   
37    /**
38    * A framework to help writing static program analysis. A subclass of
39    * this framework should specify how a single node changes the state
40    * of a program. This class finds a safe estimate (a fixed-point) for
41    * the whole program. The proven facts about the program will be
42    * annotated with
43    * {@link com.google.javascript.jscomp.graph.GraphNode#setAnnotation} to the
44    * given control flow graph's nodes in form of {@link LatticeElement}
45    * after calling {@link #analyze()}.
46    *
47    * <p>As a guideline, the following is a list of behaviors that any analysis
48    * can take:
49    * <ol>
50    * <li>Flow Direction: Is the analysis a forward or backward analysis?
51    * <li>Lattice Elements: How does the analysis represent the state of the
52    * program at any given point?
53    * <li>JOIN Operation: Given two incoming paths and a lattice state value, what
54    * can the compiler conclude at the join point?
55    * <li>Flow Equations: How does an instruction modify the state of program in
56    * terms of lattice values?
57    * <li>Initial Entry Value: What can the compiler assume at the beginning of the
58    * program?
59    * <li>Initial Estimate: What can the compiler assume at each point of the
60    * program? (What is the BOTTOM value of the lattice) By definition this lattice
61    * JOIN {@code x} for any {@code x} must also be {@code x}.
62    * </ol>
63    * To make these behaviors known to the framework, the following steps must be
64    * taken.
65    * <ol>
66    * <li>Flow Direction: Implement {@link #isForward()}.
67    * <li>Lattice Elements: Implement {@link LatticeElement}.
68    * <li>JOIN Operation: Implement
69    * {@link JoinOp#apply}.
70    * <li>Flow Equations: Implement
71    * {@link #flowThrough(Object, LatticeElement)}.
72    * <li>Initial Entry Value: Implement {@link #createEntryLattice()}.
73    * <li>Initial Estimate: Implement {@link #createInitialEstimateLattice()}.
74    * </ol>
75    *
76    * <p>Upon execution of the {@link #analyze()} method, nodes of the input
77    * control flow graph will be annotated with a {@link FlowState} object that
78    * represents maximum fixed point solution. Any previous annotations at the
79    * nodes of the control flow graph will be lost.
80    *
81    *
82    * @param <N> The control flow graph's node value type.
83    * @param <L> Lattice element type.
84    */
 
85    abstract class DataFlowAnalysis<N, L extends LatticeElement> {
86   
87    private final ControlFlowGraph<N> cfg;
88    final JoinOp<L> joinOp;
89    protected final Set<DiGraphNode<N, Branch>> orderedWorkSet;
90   
91    /*
92    * Feel free to increase this to a reasonable number if you are finding that
93    * more and more passes need more than 200000 steps before finding a
94    * fixed-point. If you just have a special case, consider calling
95    * {@link #analyse(int)} instead.
96    */
97    public static final int MAX_STEPS = 200000;
98   
99    /**
100    * Constructs a data flow analysis.
101    *
102    * <p>Typical usage
103    * <pre>
104    * DataFlowAnalysis dfa = ...
105    * dfa.analyze();
106    * </pre>
107    *
108    * {@link #analyze()} annotates the result to the control flow graph by
109    * means of {@link DiGraphNode#setAnnotation} without any
110    * modification of the graph itself. Additional calls to {@link #analyze()}
111    * recomputes the analysis which can be useful if the control flow graph
112    * has been modified.
113    *
114    * @param targetCfg The control flow graph object that this object performs
115    * on. Modification of the graph requires a separate call to
116    * {@link #analyze()}.
117    *
118    * @see #analyze()
119    */
 
120  79154 toggle DataFlowAnalysis(ControlFlowGraph<N> targetCfg, JoinOp<L> joinOp) {
121  79154 this.cfg = targetCfg;
122  79154 this.joinOp = joinOp;
123  79154 Comparator<DiGraphNode<N, Branch>> nodeComparator =
124    cfg.getOptionalNodeComparator(isForward());
125  79154 if (nodeComparator != null) {
126  79145 this.orderedWorkSet = Sets.newTreeSet(nodeComparator);
127    } else {
128  9 this.orderedWorkSet = Sets.newLinkedHashSet();
129    }
130    }
131   
132    /**
133    * Returns the control flow graph that this analysis was performed on.
134    * Modifications can be done on this graph, however, the only time that the
135    * annotations are correct is after {@link #analyze()} is called and before
136    * the graph has been modified.
137    */
 
138  1741767 toggle final ControlFlowGraph<N> getCfg() {
139  1741767 return cfg;
140    }
141   
142    /**
143    * Returns the lattice element at the exit point.
144    */
 
145  0 toggle L getExitLatticeElement() {
146  0 DiGraphNode<N, Branch> node = getCfg().getImplicitReturn();
147  0 FlowState<L> state = node.getAnnotation();
148  0 return state.getIn();
149    }
150   
 
151  407 toggle @SuppressWarnings("unchecked")
152    protected L join(L latticeA, L latticeB) {
153  407 return joinOp.apply(Lists.<L>newArrayList(latticeA, latticeB));
154    }
155   
156    /**
157    * Checks whether the analysis is a forward flow analysis or backward flow
158    * analysis.
159    *
160    * @return {@code true} if it is a forward analysis.
161    */
162    abstract boolean isForward();
163   
164    /**
165    * Computes the output state for a given node and input state.
166    *
167    * @param node The node.
168    * @param input Input lattice that should be read-only.
169    * @return Output lattice.
170    */
171    abstract L flowThrough(N node, L input);
172   
173    /**
174    * Finds a fixed-point solution using at most {@link #MAX_STEPS}
175    * iterations.
176    *
177    * @see #analyze(int)
178    */
 
179  79151 toggle final void analyze() {
180  79151 analyze(MAX_STEPS);
181    }
182   
183    /**
184    * Finds a fixed-point solution. The function has the side effect of replacing
185    * the existing node annotations with the computed solutions using {@link
186    * com.google.javascript.jscomp.graph.GraphNode#setAnnotation(Annotation)}.
187    *
188    * <p>Initially, each node's input and output flow state contains the value
189    * given by {@link #createInitialEstimateLattice()} (with the exception of the
190    * entry node of the graph which takes on the {@link #createEntryLattice()}
191    * value. Each node will use the output state of its predecessor and compute a
192    * output state according to the instruction. At that time, any nodes that
193    * depends on the node's newly modified output value will need to recompute
194    * their output state again. Each step will perform a computation at one node
195    * until no extra computation will modify any existing output state anymore.
196    *
197    * @param maxSteps Max number of iterations before the method stops and throw
198    * a {@link MaxIterationsExceededException}. This will prevent the
199    * analysis from going into a infinite loop.
200    */
 
201  79154 toggle final void analyze(int maxSteps) {
202  79154 initialize();
203  79154 int step = 0;
204  329064 while (!orderedWorkSet.isEmpty()) {
205  249913 if (step > maxSteps) {
206  3 throw new MaxIterationsExceededException(
207    "Analysis did not terminate after " + maxSteps + " iterations");
208    }
209  249910 DiGraphNode<N, Branch> curNode = orderedWorkSet.iterator().next();
210  249910 orderedWorkSet.remove(curNode);
211  249910 joinInputs(curNode);
212  249910 if (flow(curNode)) {
213    // If there is a change in the current node, we want to grab the list
214    // of nodes that this node affects.
215  234690 List<DiGraphNode<N, Branch>> nextNodes = isForward() ?
216    cfg.getDirectedSuccNodes(curNode) :
217    cfg.getDirectedPredNodes(curNode);
218  234690 for (DiGraphNode<N, Branch> nextNode : nextNodes) {
219  239821 if (nextNode != cfg.getImplicitReturn()) {
220  168610 orderedWorkSet.add(nextNode);
221    }
222    }
223    }
224  249910 step++;
225    }
226  79151 if (isForward()) {
227  71684 joinInputs(getCfg().getImplicitReturn());
228    }
229    }
230   
231    /**
232    * Gets the state of the initial estimation at each node.
233    *
234    * @return Initial state.
235    */
236    abstract L createInitialEstimateLattice();
237   
238    /**
239    * Gets the incoming state of the entry node.
240    *
241    * @return Entry state.
242    */
243    abstract L createEntryLattice();
244   
245    /**
246    * Initializes the work list and the control flow graph.
247    */
 
248  13740 toggle protected void initialize() {
249    // TODO(user): Calling clear doesn't deallocate the memory in a
250    // LinkedHashSet. Consider creating a new work set if we plan to repeatedly
251    // call analyze.
252  13740 orderedWorkSet.clear();
253  13740 for (DiGraphNode<N, Branch> node : cfg.getDirectedGraphNodes()) {
254  44187 node.setAnnotation(new FlowState<L>(createInitialEstimateLattice(),
255    createInitialEstimateLattice()));
256  44187 if (node != cfg.getImplicitReturn()) {
257  30447 orderedWorkSet.add(node);
258    }
259    }
260    }
261   
262    /**
263    * Performs a single flow through a node.
264    *
265    * @return {@code true} if the flow state differs from the previous state.
266    */
 
267  31433 toggle protected boolean flow(DiGraphNode<N, Branch> node) {
268  31433 FlowState<L> state = node.getAnnotation();
269  31433 if (isForward()) {
270  12123 L outBefore = state.out;
271  12123 state.out = flowThrough(node.getValue(), state.in);
272  12123 return !outBefore.equals(state.out);
273    } else {
274  19310 L inBefore = state.in;
275  19310 state.in = flowThrough(node.getValue(), state.out);
276  19310 return !inBefore.equals(state.in);
277    }
278    }
279   
280    /**
281    * Computes the new flow state at a given node's entry by merging the
282    * output (input) lattice of the node's predecessor (successor).
283    *
284    * @param node Node to compute new join.
285    */
 
286  37703 toggle protected void joinInputs(DiGraphNode<N, Branch> node) {
287  37703 FlowState<L> state = node.getAnnotation();
288  37703 if (isForward()) {
289  18393 if (cfg.getEntry() == node) {
290  6273 state.setIn(createEntryLattice());
291    } else {
292  12120 List<DiGraphNode<N, Branch>> inNodes = cfg.getDirectedPredNodes(node);
293  12120 if (inNodes.size() == 1) {
294  11619 FlowState<L> inNodeState = inNodes.get(0).getAnnotation();
295  11619 state.setIn(inNodeState.getOut());
296  501 } else if (inNodes.size() > 1) {
297  477 List<L> values = new ArrayList<L>(inNodes.size());
298  477 for (DiGraphNode<N, Branch> currentNode : inNodes) {
299  966 FlowState<L> currentNodeState = currentNode.getAnnotation();
300  966 values.add(currentNodeState.getOut());
301    }
302  477 state.setIn(joinOp.apply(values));
303    }
304    }
305    } else {
306  19310 List<DiGraphNode<N, Branch>> inNodes = cfg.getDirectedSuccNodes(node);
307  19310 if (inNodes.size() == 1) {
308  18353 DiGraphNode<N, Branch> inNode = inNodes.get(0);
309  18353 if (inNode == cfg.getImplicitReturn()) {
310  7305 state.setOut(createEntryLattice());
311    } else {
312  11048 FlowState<L> inNodeState = inNode.getAnnotation();
313  11048 state.setOut(inNodeState.getIn());
314    }
315  957 } else if (inNodes.size() > 1) {
316  954 List<L> values = new ArrayList<L>(inNodes.size());
317  954 for (DiGraphNode<N, Branch> currentNode : inNodes) {
318  1908 FlowState<L> currentNodeState = currentNode.getAnnotation();
319  1908 values.add(currentNodeState.getIn());
320    }
321  954 state.setOut(joinOp.apply(values));
322    }
323    }
324    }
325   
326    /**
327    * The in and out states of a node.
328    *
329    * @param <L> Input and output lattice element type.
330    */
 
331    static class FlowState<L extends LatticeElement> implements Annotation {
332    private L in;
333    private L out;
334   
335    /**
336    * Private constructor. No other classes should create new states.
337    *
338    * @param inState Input.
339    * @param outState Output.
340    */
 
341  44187 toggle private FlowState(L inState, L outState) {
342  44187 Preconditions.checkNotNull(inState);
343  44187 Preconditions.checkNotNull(outState);
344  44187 this.in = inState;
345  44187 this.out = outState;
346    }
347   
 
348  32381 toggle L getIn() {
349  32381 return in;
350    }
351   
 
352  18369 toggle void setIn(L in) {
353  18369 Preconditions.checkNotNull(in);
354  18369 this.in = in;
355    }
356   
 
357  22876 toggle L getOut() {
358  22876 return out;
359    }
360   
 
361  19307 toggle void setOut(L out) {
362  19307 Preconditions.checkNotNull(out);
363  19307 this.out = out;
364    }
365   
 
366  0 toggle @Override
367    public String toString() {
368  0 return String.format("IN: %s OUT: %s", in, out);
369    }
370   
 
371  0 toggle @Override
372    public int hashCode() {
373  0 return Objects.hashCode(in, out);
374    }
375    }
376   
377    /**
378    * The exception to be thrown if the analysis has been running for a long
379    * number of iterations. Chances are the analysis is not monotonic, a
380    * fixed-point cannot be found and it is currently stuck in an infinite loop.
381    */
 
382    static class MaxIterationsExceededException extends RuntimeException {
383    private static final long serialVersionUID = 1L;
 
384  3 toggle MaxIterationsExceededException(String msg) {
385  3 super(msg);
386    }
387    }
388   
 
389    abstract static class BranchedForwardDataFlowAnalysis
390    <N, L extends LatticeElement> extends DataFlowAnalysis<N, L> {
391   
 
392  65414 toggle @Override
393    protected void initialize() {
394  65414 orderedWorkSet.clear();
395  65414 for (DiGraphNode<N, Branch> node : getCfg().getDirectedGraphNodes()) {
396  283526 int outEdgeCount = getCfg().getOutEdges(node.getValue()).size();
397  283526 List<L> outLattices = Lists.newArrayList();
398  506844 for (int i = 0; i < outEdgeCount; i++) {
399  223318 outLattices.add(createInitialEstimateLattice());
400    }
401  283526 node.setAnnotation(new BranchedFlowState<L>(
402    createInitialEstimateLattice(), outLattices));
403  283526 if (node != getCfg().getImplicitReturn()) {
404  218112 orderedWorkSet.add(node);
405    }
406    }
407    }
408   
 
409  65414 toggle BranchedForwardDataFlowAnalysis(ControlFlowGraph<N> targetCfg,
410    JoinOp<L> joinOp) {
411  65414 super(targetCfg, joinOp);
412    }
413   
414    /**
415    * Returns the lattice element at the exit point. Needs to be overridden
416    * because we use a BranchedFlowState instead of a FlowState; ugh.
417    */
 
418  0 toggle @Override
419    L getExitLatticeElement() {
420  0 DiGraphNode<N, Branch> node = getCfg().getImplicitReturn();
421  0 BranchedFlowState<L> state = node.getAnnotation();
422  0 return state.getIn();
423    }
424   
 
425  349000 toggle @Override
426    final boolean isForward() {
427  349000 return true;
428    }
429   
430    /**
431    * The branched flow function maps a single lattice to a list of output
432    * lattices.
433    *
434    * <p>Each outgoing edge of a node will have a corresponding output lattice
435    * in the ordered returned by
436    * {@link com.google.javascript.jscomp.graph.DiGraph#getOutEdges(Object)}
437    * in the returned list.
438    *
439    * @return A list of output values depending on the edge's branch type.
440    */
441    abstract List<L> branchedFlowThrough(N node, L input);
442   
 
443  218477 toggle @Override
444    protected final boolean flow(DiGraphNode<N, Branch> node) {
445  218477 BranchedFlowState<L> state = node.getAnnotation();
446  218477 List<L> outBefore = state.out;
447  218477 state.out = branchedFlowThrough(node.getValue(), state.in);
448  218477 Preconditions.checkState(outBefore.size() == state.out.size());
449  218838 for (int i = 0; i < outBefore.size(); i++) {
450  218533 if (!outBefore.get(i).equals(state.out.get(i))) {
451  218172 return true;
452    }
453    }
454  305 return false;
455    }
456   
 
457  283891 toggle @Override
458    protected void joinInputs(DiGraphNode<N, Branch> node) {
459  283891 BranchedFlowState<L> state = node.getAnnotation();
460  283891 List<DiGraphNode<N, Branch>> predNodes =
461    getCfg().getDirectedPredNodes(node);
462  283891 List<L> values = new ArrayList<L>(predNodes.size());
463   
464  283891 for (DiGraphNode<N, Branch> predNode : predNodes) {
465  223903 BranchedFlowState<L> predNodeState = predNode.getAnnotation();
466   
467  223903 L in = predNodeState.out.get(
468    getCfg().getDirectedSuccNodes(predNode).indexOf(node));
469   
470  223903 values.add(in);
471    }
472  283891 if (getCfg().getEntry() == node) {
473  65414 state.setIn(createEntryLattice());
474  218477 } else if (!values.isEmpty()) {
475  218435 state.setIn(joinOp.apply(values));
476    }
477    }
478    }
479   
480    /**
481    * The in and out states of a node.
482    *
483    * @param <L> Input and output lattice element type.
484    */
 
485    static class BranchedFlowState<L extends LatticeElement>
486    implements Annotation {
487    private L in;
488    private List<L> out;
489   
490    /**
491    * Private constructor. No other classes should create new states.
492    *
493    * @param inState Input.
494    * @param outState Output.
495    */
 
496  283526 toggle private BranchedFlowState(L inState, List<L> outState) {
497  283526 Preconditions.checkNotNull(inState);
498  283526 Preconditions.checkNotNull(outState);
499  283526 this.in = inState;
500  283526 this.out = outState;
501    }
502   
 
503  270 toggle L getIn() {
504  270 return in;
505    }
506   
 
507  283849 toggle void setIn(L in) {
508  283849 Preconditions.checkNotNull(in);
509  283849 this.in = in;
510    }
511   
 
512  0 toggle List<L> getOut() {
513  0 return out;
514    }
515   
 
516  0 toggle void setOut(List<L> out) {
517  0 Preconditions.checkNotNull(out);
518  0 for (L item : out) {
519  0 Preconditions.checkNotNull(item);
520    }
521  0 this.out = out;
522    }
523   
 
524  0 toggle @Override
525    public String toString() {
526  0 return String.format("IN: %s OUT: %s", in, out);
527    }
528   
 
529  0 toggle @Override
530    public int hashCode() {
531  0 return Objects.hashCode(in, out);
532    }
533    }
534   
535    /**
536    * Compute set of escaped variables. When a variable is escaped in a
537    * dataflow analysis, it can be reference outside of the code that we are
538    * analyzing. A variable is escaped if any of the following is true:
539    *
540    * <p><ol>
541    * <li>It is defined as the exception name in CATCH clause so it became a
542    * variable local not to our definition of scope.</li>
543    * <li>Exported variables as they can be needed after the script terminates.
544    * </li>
545    * <li>Names of named functions because in JavaScript, <i>function foo(){}</i>
546    * does not kill <i>foo</i> in the dataflow.</li>
547    */
 
548  13731 toggle static void computeEscaped(final Scope jsScope, final Set<Var> escaped,
549    AbstractCompiler compiler) {
550    // TODO(user): Very good place to store this information somewhere.
551  13731 AbstractPostOrderCallback finder = new AbstractPostOrderCallback() {
 
552  87207 toggle @Override
553    public void visit(NodeTraversal t, Node n, Node parent) {
554  87207 if (jsScope == t.getScope() || !n.isName()
555    || parent.isFunction()) {
556  86727 return;
557    }
558  480 String name = n.getString();
559  480 Var var = t.getScope().getVar(name);
560  480 if (var != null && var.scope == jsScope) {
561  162 escaped.add(jsScope.getVar(name));
562    }
563    }
564    };
565   
566  13731 NodeTraversal t = new NodeTraversal(compiler, finder);
567  13731 t.traverseAtScope(jsScope);
568   
569    // 1: Remove the exception name in CATCH which technically isn't local to
570    // begin with.
571  25878 for (Iterator<Var> i = jsScope.getVars(); i.hasNext();) {
572  12147 Var var = i.next();
573  12147 if (var.getParentNode().isCatch() ||
574    compiler.getCodingConvention().isExported(var.getName())) {
575  264 escaped.add(var);
576    }
577    }
578    }
579    }
  • Report generated by OpenClover v 4.4.1 on Mon Jan 2 2023 15:17:08 MST using coverage data from Mon Jan 2 2023 15:16:37 MST.
  • OpenClover is free and open-source software.